#include "predictor.h"
#include <stdlib.h>
#include <stdio.h>
#include <iostream>
#include <fstream>
#include <string>
#include <math.h>

using namespace std;

#pragma mark - COUNTERS.H 
// ---------------------------------------------------------------------------------------------------------------------
// COUNTERS.h
// ---------------------------------------------------------------------------------------------------------------------
// Project:	Alpha Branch Predictor
// Authors:	Jabeer Ahmed, 
// 			Omar Mohsin, 
// 			Fadi Butti
// Course:	ECE - 586 (Winter 2013)
// Prof:	Mark Faust
// Portland State University
// ---------------------------------------------------------------------------------------------------------------------

#ifndef __COUNTERS_H__
#define __COUNTERS_H__

using namespace std;
class counter2
{
public:
	uint bits:2;
    uint size;
	counter2()			:bits(3),size(2){};                                 // Default Constructor
	counter2(int val)	:bits(val){};
	counter2(char val)	:bits(val){};
	counter2(short val)	:bits(val){};
	counter2(uint val)	:bits(val){};

	counter2& operator++(int){if(bits<3)this->bits++; return *this;}    // Increment Counter 
	counter2& operator--(int){if(bits>0)this->bits--; return *this;}    // Decrement Counter
	bool   isTaken()	{ return bits & 0x2;}                           // Return the MSB
	string isTakenStr()	{ return (isTaken()) ? string("taken"):string("not taken");}
    friend ostream& operator<<(ostream& lhs, const counter2& rhs)       // Print
    {
        lhs << (bool)(rhs.bits & 0x2) << (bool)(rhs.bits & 0x1);
        return lhs;
    }
};

class counter3
{
public:
	uint bits:3;
    uint size;
	counter3()			:bits(7),size(3) {};                                   // Constructors 
	counter3(int val)	:bits(val){};
	counter3(char val)	:bits(val){};
	counter3(short val)	:bits(val){};
	counter3(uint val)	:bits(val){};
	string isTakenStr()	{ return (isTaken()) ? string("taken"):string("not taken");}
	counter3& operator++(int){if(bits<7)this->bits++; return *this;}    // Increment Counter
	counter3& operator--(int){if(bits>0)this->bits--; return *this;}    // Decrement Counter
	bool   isTaken()	{ return bits & 0x4;}                           // Return MSB
    friend ostream& operator<<(ostream& lhs, const counter3& rhs)       // Print
    {
        lhs << (bool)(rhs.bits & 0x4) << (bool)(rhs.bits & 0x2) << (bool)(rhs.bits & 0x1);
        return lhs;
    }
};
#endif 	// __COUNTERS_H__

#pragma mark - SHIFT_REGISTERS.H 
// ---------------------------------------------------------------------------------------------------------------------
// SHIFT_REGISTERS.h
// ---------------------------------------------------------------------------------------------------------------------
// Project:	Alpha Branch Predictor
// Authors:	Jabeer Ahmed, 
// 			Omar Mohsin, 
// 			Fadi Butti
// Course:	ECE - 586 (Winter 2013)
// Prof:	Mark Faust
// Portland State University
// ---------------------------------------------------------------------------------------------------------------------

#ifndef __SHIFT_REGISTERS_H__
#define __SHIFT_REGISTERS_H__

class shift_reg 						
{
public:
	uint bits;                                      // bool array for storing bits
	uint size; 										// size of the register
    uint mask;
    
	shift_reg(int len){  							// contructor with length as input
		bits = 0;                                   // Make the bool array of size len
		size = len; 								// set size of register to len
        mask = 1;                                   // mask = 0x1
        mask<<=size;                                // shift that 1 till it reaches bit size
        mask--;                                     // Decrement mask to get all ones (mask)
    }
    
    shift_reg(const shift_reg& reg){                
        this->size = reg.size;
        this->bits = reg.bits;
        this->mask = reg.mask;
    }
    
    shift_reg& operator= (const shift_reg& reg){
        if (this != &reg){
            this->size = reg.size;
            this->bits = reg.bits;
            this->mask = reg.mask;
        }
        return *this;
    }
    
	void push(bool bit){ 							// pushes bits in and calcs the value of the register
        bits<<=1;                                   // shift left by 1
        bits|=bit;                                  // or with the input bit to set LSB = input bit
        bits&=mask;                                 // apply mask 
    }
    
    friend ostream& operator<<(ostream& lhs, const shift_reg& rhs) 	// prints out the bits
    {																// e.g. usage: cout << reg << endl;
        uint m = 1<<(rhs.size-1);
        
        for (int i=rhs.size; i>0;i--){
            if (i%4 == 0) 
                lhs << " ";
			lhs << (bool)(rhs.bits & m); 
            m>>=1;
		}
        return lhs;
    }
};
#endif 	// __SHIFT_REGISTERS_H__

#pragma mark - LRU
// ---------------------------------------------------------------------------------------------------------------------
// LRU.h
// ---------------------------------------------------------------------------------------------------------------------
// Project:	Alpha Branch Predictor
// Authors:	Jabeer Ahmed, 
// 			Omar Mohsin, 
// 			Fadi Butti
// Course:	ECE - 586 (Winter 2013)
// Prof:	Mark Faust
// Portland State University
// ---------------------------------------------------------------------------------------------------------------------

#ifndef __LRU_H__
#define __LRU_H__

class LRU {
public:
    virtual int lru_way(){return 0;};
    virtual void lru_update(unsigned int way){};    
};

class LRU_4_way : public LRU{
    bool bits[6];     
public:
    friend ostream& operator<<(ostream& lhs, const LRU_4_way& rhs)
    {
        lhs << rhs.bits[0] << rhs.bits[1] << rhs.bits[2] << rhs.bits[3] << rhs.bits[4] << rhs.bits[5]; 
        return lhs;
    }
    LRU_4_way(){
        bits[0]=bits[1]=bits[2]=0;
        bits[3]=bits[4]=bits[5]=0;        
    }
    
    virtual int lru_way()
    {
        int way = -1;
        if (!bits[0] && !bits[1] && !bits[2])
            way = 0;
        else if ( bits[0] && !bits[3] && !bits[4])
            way = 1;
        else if ( bits[1] &&  bits[3] && !bits[5])
            way = 2;
        else if ( bits[2] &&  bits[4] &&  bits[5])
            way = 3;
        
        return way;
    }
    
    virtual void lru_update(unsigned int way)
    {
        if (way<4) {
            switch (way) {
                case 0:
                    bits[0] = 1;
                    bits[1] = 1;
                    bits[2] = 1;
                    break;
                case 1:    
                    bits[0] = 0;
                    bits[3] = 1;
                    bits[4] = 1;
                    break;
                case 2:
                    bits[1] = 0;
                    bits[3] = 0;
                    bits[5] = 1;
                    break;
                case 3:
                    bits[2] = 0;
                    bits[4] = 0;
                    bits[5] = 0;
                    break;
            }
        }else{
            cout << "incorrect way = " << way << endl;;
        }
    }
};

class LRU_2_way : public LRU {
    uint bits[1];     
public:
    friend ostream& operator<<(ostream& lhs, const LRU_2_way& rhs)
    {
        lhs << rhs.bits; 
        return lhs;
    }
    LRU_2_way(){
        bits[0] = 0;
    }
    
    int lru_way(){return !bits[0];}
    
    void lru_update(unsigned int way)
    {
        if (way<2) 
            bits[0] = way;
        else
            cout << "incorrect way = " << way << endl;;
    }
};
#endif 	// __LRU_H__

#pragma mark - BRANCH_TARGET_PREDICTOR.H 
// ---------------------------------------------------------------------------------------------------------------------
// BRANCH_TARGET_PREDICTOR.h
// ---------------------------------------------------------------------------------------------------------------------
// Project:	Alpha Branch Predictor
// Authors:	Jabeer Ahmed, 
// 			Omar Mohsin, 
// 			Fadi Butti
// Course:	ECE - 586 (Winter 2013)
// Prof:	Mark Faust
// Portland State University
// ---------------------------------------------------------------------------------------------------------------------

#ifndef __BRANCH_TARGET_PREDICTOR_H__
#define __BRANCH_TARGET_PREDICTOR_H__

class branch_target_entry{
	uint target_ins_addr;		// The target instruction address
	uint tag;					// Tag bits
	uint shift_tag_bits;		// num tag bits
	
public:	
	uint size;                  // size of the entry
	
	branch_target_entry(uint indexSize){
		shift_tag_bits = 32-indexSize;	// Number of shifts needed to get tag from PC
		tag = 0;						// Set tag to 0
		target_ins_addr = 0;			// 
		size = indexSize + 32;          // size of entry = tagsize + 32 bits target + 1 bit valid
	}
 	
	uint get_target_address(unsigned int pc){
		if (tag == (pc >> shift_tag_bits))   // If the entry is valid and the tags match PC
			return target_ins_addr;                     // Return target address
		else                                            // Else
			return 0x0;                                 // Return 0
	}
	
	uint set_target_address(uint pc, uint target_addr){ 
		tag = (pc >> shift_tag_bits);                   // extract tag bits from PC
		target_ins_addr = target_addr;                  // set the target address
		return target_ins_addr;                         // return target address
	}
};

class assosiative_branch_target_entry{

    vector <branch_target_entry> _set;
    LRU* _lru;
    uint _numsets;

    
public:    
    uint size;
    
    assosiative_branch_target_entry(uint indexSize, uint numsets)
    {
        if (numsets == 3 || numsets > 4) 
            numsets = 4;
        if (numsets == 0)
            numsets = 1;
        
        _numsets = numsets;
        for (int i = 0; i < _numsets; i++) {             
            _set.push_back(branch_target_entry(indexSize));
        }
        if (_numsets == 1)           
            _lru = new LRU();            // 0 way LRU
        else if (_numsets == 2)
            _lru = new LRU_2_way();      // 2 way LRU
        else if (_numsets == 4)
            _lru = new LRU_4_way();      // 4 way LRU
        
        size = _set[0].size * _numsets + _numsets; // size of entry * number of sets + tag bits
    }
    
    uint get_prediction(uint pc)
    {
        uint target = 0x0;
        uint i = 0;
        do{
            target = _set[i].get_target_address(pc);
        }while (target == 0x0 && ++i<_numsets);
        if (i < _numsets)
            _lru->lru_update(i);
        return target;
    }
    
    void update_prediction(uint pc, uint target_address)
    {
        uint target = 0x0;
        int i = 0;
        do{
            target = _set[i].get_target_address(pc);
        }while (target == 0x0 && ++i<_numsets);        
        if (i == _numsets){
            i = _lru->lru_way();
            _set[i].set_target_address(pc, target_address); 
            _lru->lru_update(i);
        }        
    }
    
    uint set_size(){
        return _set[0].size;
    }
};

class branch_target_predictor {
    
	vector <assosiative_branch_target_entry> table;	// Branch target prediction table;
	uint num_tag_bits;                              // Size of tag
    uint num_indx_bits;
public:  
	uint size;                                      // Size of the table in bits  
    uint table_length;                              // length of the table
    uint numsets;
    
	branch_target_predictor(int length, uint numsets)
	{
        this->numsets = numsets;
		table_length = length;
		num_indx_bits = log(table_length)/log(2);
        num_tag_bits = 32 - num_indx_bits;
		for (uint i=0; i<table_length; i++)
			table.push_back(assosiative_branch_target_entry(num_tag_bits,numsets));	
        size = table_length * table[0].size;
	}
    
    uint entry_size(){
        return table[0].size;
    }
    
    uint set_size(){
        return table[0].set_size();
    }
    
	uint indexFor(uint pc)
	{
		return (pc) & (table_length-1);
	}
	
	uint get_prediction(uint pc)
	{
		uint indx = indexFor(pc);
		uint addr = table[indx].get_prediction(pc);
		return addr;
	}
	
	void update_prediction(uint pc, uint target_addr)
	{
		uint indx = indexFor(pc);
		table[indx].update_prediction(pc,target_addr);
	}
};

#endif 	// __BRANCH_TARGET_PREDICTOR_H__

#pragma mark - RETURN_STACK.H 
// ---------------------------------------------------------------------------------------------------------------------
// RETURN_STACK.h
// ---------------------------------------------------------------------------------------------------------------------
// Project:	Alpha Branch Predictor
// Authors:	Jabeer Ahmed, 
// 			Omar Mohsin, 
// 			Fadi Butti
// Course:	ECE - 586 (Winter 2013)
// Prof:	Mark Faust
// Portland State University
// ---------------------------------------------------------------------------------------------------------------------

#ifndef __RETURN_STACK_H__
#define __RETURN_STACK_H__

class return_stack {
    
    uint *head;
    uint *tail;
public:    
    uint depth;
    uint size;
    return_stack(int length){
        depth = length;
        head = (uint*)calloc(depth, sizeof(int));
        tail = head;
        size = length*32;
    }
    ~return_stack(){
        free(head);
    }
    
    void push(uint address)
    {   
        long int len = tail-head;
        for (int i = 0; i<len; i++)
            *(tail-i) = *(tail-i-1);
        *(head) = address;
        tail++;
        long unsigned int cur_size = tail-head;
        if(cur_size > depth)
            tail--;
    }
    
    uint pop()
    {   
        long int len = tail-head;
        if (len == 0)
            return 0;
        
        uint ret = *head;
        for (int i = 0; i < len; i++)
            *(head+i) = *(head+i+1);
        tail--;
        long int cur_size = tail-head;
        if(cur_size < 0)
            tail++;
        return ret;
    }
    
    void print(){
        for (int i = 0; i < (tail-head); i++) {
            cout << head[i] << endl;
        }
    }
};

#endif // __RETURN_STACK_H__

#pragma mark - LOCAL_HISTORY_TABLE.H 
// ---------------------------------------------------------------------------------------------------------------------
// LOCAL_HISTORY_TABLE.h
// ---------------------------------------------------------------------------------------------------------------------
// Project:	Alpha Branch Predictor
// Authors:	Jabeer Ahmed, 
// 			Omar Mohsin, 
// 			Fadi Butti
// Course:	ECE - 586 (Winter 2013)
// Prof:	Mark Faust
// Portland State University
// ---------------------------------------------------------------------------------------------------------------------

#ifndef __LOCAL_HISTORY_TABLE_H__
#define __LOCAL_HISTORY_TABLE_H__

#define DEFAULT_LOCAL_TABLE_SIZE 1024
#define DEFAULT_HISTORY_PATTERN_SIZE 10

using namespace std;

class local_history_table {
	vector<shift_reg> table;
public:
    uint size;
    uint table_length;

    uint pattern_width;

	local_history_table():table_length(DEFAULT_LOCAL_TABLE_SIZE),pattern_width(DEFAULT_HISTORY_PATTERN_SIZE)
    {
		for (uint i=0; i<table_length; i++)
            table.push_back(shift_reg(pattern_width));
        size = table_length*pattern_width;
    }
	local_history_table(uint length, uint width):table_length(length),pattern_width(width)
    {
		for (uint i=0; i<table_length; i++)
            table.push_back(shift_reg(pattern_width));
        size = table_length*pattern_width;
	}
    inline uint indexFor(uint pc)
    {
        return pc & (table_length - 1);             
    }
	shift_reg& operator[] (int pc){
		return table[indexFor(pc)];
	}
    void print()
    {
        for (uint i =0; i<table_length; i++) {
            printf("%6d. ",i);
            cout << table[i] << endl;
        }
    }
};

class local_prediction_table {
	counter3 *table;
public:
    uint table_length;
    uint size;

	local_prediction_table(){
		table = new  counter3[DEFAULT_LOCAL_TABLE_SIZE];
        table_length = DEFAULT_LOCAL_TABLE_SIZE;
        size = table_length*3;
	}
	local_prediction_table(int length):table_length(length){
		table = new  counter3[table_length];
        size = table_length*3;
	}
	~local_prediction_table(){
		delete table;
	}
    inline uint indexFor(uint indx)
    {
        return indx & (table_length - 1);
    }
	counter3& operator[] (int indx){
		return table[indexFor(indx)];
	}
    void print()
    {
        for (uint i=0; i<table_length; i++) {
            printf("%6d. ",i);
            cout << table[i] << endl;
        }
    }
};


#endif 	// __LOCAL_HISTORY_TABLE_H__

#pragma mark - GLOBAL_PREDICTION_TABLE.H 
// ---------------------------------------------------------------------------------------------------------------------
// GLOBAL_PREDICTION_TABLE.h
// ---------------------------------------------------------------------------------------------------------------------
// Project:	Alpha Branch Predictor
// Authors:	Jabeer Ahmed, 
// 			Omar Mohsin, 
// 			Fadi Butti
// Course:	ECE - 586 (Winter 2013)
// Prof:	Mark Faust
// Portland State University
// ---------------------------------------------------------------------------------------------------------------------

#ifndef __GLOBAL_PREDICTION_TABLE_H__
#define __GLOBAL_PREDICTION_TABLE_H__

#define DEFAULT_GLOBAL_TABLE_SIZE 4096

class global_prediction_table {
	counter2 *table;
public:
    uint table_length;
    uint size;
    
	global_prediction_table(){
		table = new  counter2[DEFAULT_GLOBAL_TABLE_SIZE];
        table_length = DEFAULT_GLOBAL_TABLE_SIZE;
        size = table_length * table[0].size;                // size in bits
	}
	global_prediction_table(int length):table_length(length){
		table = new  counter2[length];
        size = table_length * table[0].size;                // size in bits
	}
	~global_prediction_table(){
		delete table;
	}
    inline uint indexFor(uint indx)
    {
        return indx & (table_length - 1);
    }
	counter2& operator[] (uint indx){
		return table[indexFor(indx)];
	}
    void print()
    {
        for (uint i=0; i<table_length; i++) {
            printf("%6d. ",i);
            cout << table[i] << endl;
        }
    }
};

class choice_prediction {
	counter2 *table;
public:
    uint table_length;
    uint size;
    
	choice_prediction(){
		table = new  counter2[DEFAULT_GLOBAL_TABLE_SIZE];
        table_length = DEFAULT_GLOBAL_TABLE_SIZE;
        size = table_length * table[0].size;                // size in bits
	}
	choice_prediction(int length):table_length(length){
		table = new  counter2[length];
        size = table_length * table[0].size;                // size in bits
	}
	~choice_prediction(){
		delete table;
	}
    inline uint indexFor(uint indx)
    {
        return indx & (table_length - 1);
    }
	counter2& operator[] (uint indx){
		return table[indexFor(indx)];
	} 
    void print()
    {
        for (uint i=0; i<table_length; i++) {
            printf("%6d. ",i);
            cout << table[i] << endl;
        }
    }
};

#endif 	// __GLOBAL_PREDICTION_TABLE_H__

// ---------------------------------------------------------------------------------------------------------------------
// DEBUGGER.h
// ---------------------------------------------------------------------------------------------------------------------
// Project:	Alpha Branch Predictor
// Authors:	Jabeer Ahmed, 
// 			Omar Mohsin, 
// 			Fadi Butti
// Course:	ECE - 586 (Winter 2013)
// Prof:	Mark Faust
// Portland State University
// ---------------------------------------------------------------------------------------------------------------------

/* 
---------------------------------------------------------------------------------------------------------------------
Redefinition of branch_record_c & op_state_c
---------------------------------------------------------------------------------------------------------------------
These classes will defined only if the debugger is compiled without the framework 
for debugging purpose. This will allow for the debugger to read the ASCII text file 
without the need to compile the framework.
***** ASSUMING THAT tread.h & op_state.h WILL BE COMPILED BEFORE THIS FILE *****
*/
#ifndef TREAD_H_SEEN
struct branch_record_c
{
    uint   instruction_addr;       // the branch's PC (program counter)                      
    uint   instruction_next_addr;  // the PC of the static instruction following the branch  
    bool   is_indirect;            // true if the target is computed; false if it's PC-rel; returns are also considered indirect
    bool   is_conditional;         // true if the branch is conditional; false otherwise     
    bool   is_call;                // true if the branch is a call; false otherwise          
    bool   is_return;              // true if the branch is a return; false otherwise        
    bool   is_taken;
    branch_record_c(){
        instruction_addr        = 0;     
        instruction_next_addr   = 0; 
        is_indirect             = false;          
        is_conditional          = false;       
        is_call                 = false;             
        is_return               = false;
        is_taken                = false;
    }
};

struct op_state_c
{
	/* data */
};
#endif

#pragma mark - DEBUGGER.H 

/* 
---------------------------------------------------------------------------------------------------------------------
Debugger & Statistics   
---------------------------------------------------------------------------------------------------------------------
*/

#ifndef __DEBUGGER_H__
#define __DEBUGGER_H__

#include <stdio.h>
#include <iostream>
#include <fstream>
#include <string>
#ifdef TREAD_H_SEEN					// if the debugger is used with the framework
#include "tread.h"					// we need to include tread.h
#endif						

#define TF(tf) (tf) ? "True" : "False"
using namespace std;
struct br_stat
{
	uint num_indirect_br;
	uint num_pc_rel_br;
	uint num_conditional_br;
	uint num_unconditional_br;
	uint num_calls;
	uint num_returns;
	int  call_stack;
	uint total_call_stack;
	float avg_call_stack;
	uint max_call_stack;	
	int min_call_stack;
	
	br_stat(): 
		num_indirect_br(0),
		num_pc_rel_br(0),
		num_conditional_br(0),
		num_unconditional_br(0),
		num_calls(0),
		num_returns(0),
		call_stack(12),
		total_call_stack(0),
		avg_call_stack(0),
		max_call_stack(0),	
        min_call_stack(0){}
};

void print_branch(const branch_record_c* br)
{
     printf("%d. %s\t\t%s\t\t%s\t\t%s\n", br->instruction_addr, TF(br->is_indirect), TF(br->is_conditional),TF(br->is_call),TF(br->is_return));
}

void write_statistics(const char* file, const br_stat* stat)
{
	ofstream stat_file (file);
	if (stat_file.is_open()){
		stat_file << "Branch Statistics" << endl;
		stat_file << "num_indirect_br:\t\t" << stat->num_indirect_br << endl;
		stat_file << "num_pc_rel_br:\t\t\t" << stat->num_pc_rel_br << endl;
		stat_file << "num_conditional_br:\t\t" << stat->num_conditional_br << endl;
		stat_file << "num_unconditional_br:\t" << stat->num_unconditional_br << endl;
		stat_file << "num_calls:\t\t\t\t" << stat->num_calls << endl;
		stat_file << "num_returns:\t\t\t" << stat->num_returns << endl;
		stat_file << "call_stack:\t\t\t\t" << stat->call_stack << endl;
		stat_file << "total_call_stack:\t\t" << stat->total_call_stack << endl;
		stat_file << "avg_call_stack:\t\t\t" << stat->avg_call_stack << endl;
		stat_file << "max_call_stack:\t\t\t" << stat->max_call_stack << endl;	
		stat_file << "min_call_stack:\t\t\t" << stat->min_call_stack << endl;	
		stat_file.close();
	}
}

bool initialize_debugger(const char* file)
{
	FILE *fp = fopen(file, "w");
	bool res = false;
	if (fp){
		fprintf(fp, "Branch_PC\t\tactual_target\tis_cond\t\tis_call\t\tis_return\tis_taken\tis_indir\n");
		res = true;
	}
	fclose(fp);	
	return res;
}

void write_prediction(const char* file, const branch_record_c* br, bool taken, uint actual_target_address)
{
	FILE *fp = fopen(file,"a");
	if (fp){
		fprintf(fp, "%p\t\t%p\t\t%s\t\t%s\t\t%s\t\t%s\t\t%s\n",(void*)br->instruction_addr, (void*)actual_target_address, TF(br->is_conditional),TF(br->is_call),TF(br->is_return),TF(taken),TF(br->is_indirect));
	}
	fclose(fp);
}

#ifndef TREAD_H_SEEN
void initialize_reader(ifstream& file)
{
	string line;
	if (file.is_open() && file.good()){
		getline(file,line);
	}
}

void read_prediction(ifstream& file, branch_record_c* br)
{
    uint target, pc;
    char tf[5][8];
    string line;
	if (file.is_open() && file.good()){
		getline(file,line);
        sscanf(line.c_str(), "%x\t\t%x\t\t%s\t\t%s\t\t%s\t\t%s\t\t%s\n",&pc,&target,tf[0],tf[1],tf[2],tf[3],tf[4]);
        br->instruction_addr = pc;
        br->instruction_next_addr = target;
        br->is_conditional  = tf[0][0] == 'T';
        br->is_call         = tf[1][0] == 'T';
        br->is_return       = tf[2][0] == 'T';        
        br->is_taken        = tf[3][0] == 'T';
        br->is_indirect     = tf[4][0] == 'T';
    }
}
#endif
#endif // __DEBUGGER_H__

#pragma mark - PREDICTOR.CC 

// ---------------------------------------------------------------------------------------------------------------------
// PREDICTOR.cc
// ---------------------------------------------------------------------------------------------------------------------
// Project:	Alpha Branch Predictor
// Authors:	Jabeer Ahmed, 
// 			Omar Mohsin, 
// 			Fadi Butti
// Course:	ECE - 586 (Winter 2013)
// Prof:	Mark Faust
// Portland State University
// ---------------------------------------------------------------------------------------------------------------------
//
// Faust's Prediction
// INT-1    ~ 7.3+
// FP-1     ~ 3.3+
// MM-1     ~ 8.4+
// SERV-1   ~ 9.8+ or 17.0+
//
#include <stdlib.h>

#define NOT_TAKEN 	0
#define TAKEN 		1

using namespace std;

/*
---------------------------------------------------------------------------------------------------------------------	
Statistics
---------------------------------------------------------------------------------------------------------------------	
*/
#pragma mark - Statistics 

bool 					is_debugger_initialized = false;		// flag to initailize debugger 							//<--- Debug	
br_stat 				stat;																							//<--- Debug	
const char res_file[]  = "/Users/jabeerahmed/alpha-branch-predictor/framework/res.txt";
const char stat_file[] = "/Users/jabeerahmed/alpha-branch-predictor/framework/stat.txt";
uint 					print_counter = 0;

void update_statistics(const char* file, const branch_record_c* br)														//<--- Debug
{

	if (br->is_indirect)										// if the branch is indirect
		stat.num_indirect_br++;									// increment indirect counter
	else														// else
		stat.num_pc_rel_br++;									// increment pc_relative counter	

	if (br->is_conditional)										// if the branch is conditional
		stat.num_conditional_br++;								// increment conditional counter
	else														// else
		stat.num_unconditional_br++;							// increment unconditional counter	

	if (br->is_call){											// if its a procedure call
		stat.num_calls++;										// increment call counter
		stat.call_stack++;										// increment the call_stack depth
		stat.total_call_stack+=stat.call_stack;					// increase the total_call_stack depth
		stat.avg_call_stack = (float)stat.total_call_stack/stat.num_calls; // calculate the current average stack depth
		if (stat.call_stack > (int)stat.max_call_stack)				// check for max call stack
			stat.max_call_stack = stat.call_stack;				
	}

	if (br->is_return){											// if its a procedure return
		stat.num_returns++;										// increment the return counter
		stat.call_stack--;										// decrement the call_stack
		if (stat.call_stack < 0)
		{
			if (stat.call_stack < (int)stat.min_call_stack)		// check for min call stack
				stat.min_call_stack = stat.call_stack;				
		}
	}
	if ((++print_counter)%100 == 0)								// update the file every hundred times
		write_statistics(file, &stat);
}

/*
---------------------------------------------------------------------------------------------------------------------
OBJECTS & VARIABLES 
---------------------------------------------------------------------------------------------------------------------
*/

struct local_global_prediction {
    bool local_prediction;
    bool global_prediction;
    bool prediction;
};

#pragma mark - Variables 

uint table_length = 1024;                           // Local History Table Length
uint pattern_size = 10;                             // Local History Pattern Size
uint predictor_length = (uint)powf(2,pattern_size); // Local Predictor Length 
uint path_history_length = 12;                      // Path History Length
uint tb_length = 128;                               // Target Buffer Length
uint tb_sets = 4;                                   // Number of Target Buffer Sets
uint rs_depth = 128;                                 // R_stack depth

local_history_table     local_history(table_length, pattern_size);          // Local History Table (10-bit shift registers) 
local_prediction_table  local_predictor((uint)powf(2,pattern_size));        // Local Predictor Table (3-bit saturation counters)
shift_reg 			  	path_history(path_history_length);                  // Path History (12-bit shift register)
global_prediction_table global_predictor((uint)powf(2,path_history_length));// Global Predictor Table (2-bit saturation counters) 
choice_prediction 		prediction_chooser((uint)powf(2,path_history_length));  // Choice Prediction (2-bit saturation counters)
local_global_prediction last_prediction;                                    // 2 bits 
branch_target_predictor target_predictor(tb_length,tb_sets);
return_stack            r_stack(rs_depth);

void print_tables()
{
    cout << "Local History Table (" << local_history.table_length << " x " << local_history.pattern_width << ")" << endl;
    local_history.print();
    cout << endl;
    cout << endl;
    cout << endl;
    cout << endl;
    cout << "Local Prediction Table (" << local_predictor.table_length << " x 3)" << endl;
    local_predictor.print();
    cout << endl;
    cout << endl;
    cout << "Global Prediction Table (" << global_predictor.table_length << " x 2)" << endl;
    global_predictor.print();
    cout << endl;
    cout << endl;
    cout << "Prediction Chooser Table (" << prediction_chooser.table_length << " x 2)" << endl;
    prediction_chooser.print();
    
}

void print_system_size()
{ 
    uint alpha_total_size = local_history.size + local_predictor.size + global_predictor.size + prediction_chooser.size + path_history.size + 3;
    uint target_predictor_size = target_predictor.size + r_stack.size;
    cout << "*********************************************************" << endl;
    cout << "Alpha Predictor:" << endl;
    printf("Local History Table:               %8d x %2d = %8d bits\n", local_history.table_length, local_history.pattern_width,local_history.size);
    printf("Local Prediction Table:            %8d x %2d = %8d bits\n", local_predictor.table_length, 3,local_predictor.size);
    printf("Global Prediction Table:           %8d x %2d = %8d bits\n", global_predictor.table_length, 2, global_predictor.size);
    printf("Prediction Chooser Table:          %8d x %2d = %8d bits\n", prediction_chooser.table_length, 2,prediction_chooser.size);    
    printf("Path History:                      %8d x %2d = %8d bits\n", 1, path_history.size,path_history.size);    
    printf("Last Prediction:                   %8d x %2d = %8d bits\n", 1, 3, 3);    
    printf("-----------------------------------------------------------------\n");
    printf("Total Alpha Predictor Size                       = %8d bits\n",alpha_total_size);
    printf("                                                 = %8.2f kB\n",(float)alpha_total_size/1024/8);
    printf("Remaining Bits                                   = %8d bits\n", 64*1024 - alpha_total_size);
    
    cout << endl;
    cout << "Target Predictor:" << endl;
    printf("Target Buffer Length:                            = %8d\n", target_predictor.table_length);
    printf("Target Buffer Number of Sets:                    = %8d\n", target_predictor.numsets);    
    printf("Target Buffer entry size:                        = %8d\n", target_predictor.entry_size());
    printf("Target Buffer set size:                          = %8d\n", target_predictor.set_size());
    printf("Target Buffer Size:                              = %8d\n", target_predictor.size);
    printf("Return Buffer Size:                %8d x %2d = %8d bits\n", 1, r_stack.depth, r_stack.size);    
    printf("-----------------------------------------------------------------\n");
    printf("Total Predictor Size:                            = %8d bits\n", target_predictor_size);
    printf("Total Size:                                      = %8d bits\n", alpha_total_size + target_predictor_size);
    printf("Remaining Bits                                   = %8d bits\n", 64*1024 - alpha_total_size - target_predictor_size);
}

/* 
---------------------------------------------------------------------------------------------------------------------
ALPHA BRANCH PREDICTOR - Refer to fig: 4 of "The Alpha 21264 microprocessor" paper for an illustrative description 
---------------------------------------------------------------------------------------------------------------------
BRANCH TARGET PREDICTION 
---------------------------------------------------------------------------------------------------------------------
*/
#pragma mark - Branch Predictor

void update_prediction_chooser(const branch_record_c *br, uint outcome)
{
    bool local_mispredict   = last_prediction.local_prediction != outcome;
    bool global_mispredict  = last_prediction.global_prediction != outcome;

    if (local_mispredict != global_mispredict) {
        if (local_mispredict)                       // if local mispredict
            prediction_chooser[path_history.bits]++; // Increment the counter towards global
        else                                        // if global mispredict
            prediction_chooser[path_history.bits]--; // Decrement the counter towards local 
    }
}

void update_global_branch_prediction(const branch_record_c *br, uint outcome){
    uint path_hist = path_history.bits;                          // Get the path_history
    if (outcome == TAKEN)                                       // If the outcome was Taken
        global_predictor[path_hist]++;                          // increment counter
    else                                                        // else if Not taken
        global_predictor[path_hist]--;                          // decrement counter
    
}

void update_local_branch_prediction(const branch_record_c *br, uint outcome){
    
    uint pc = br->instruction_addr;                             // Get the Current PC
    uint pattern = local_history[pc].bits;                       // Get the local history pattern at the index
    if (outcome == TAKEN)                                       // If the outcome is Taken
        local_predictor[pattern]++;                             // Increment the local_predictor counter
    else                                                        // If it is not taken
        local_predictor[pattern]--;                             // Decrement the local_predictor counter    
    
    local_history[pc].push(outcome);                            // push the outcome in the shift-register    
}

bool global_branch_prediction(const branch_record_c* br)
{
    uint path_hist = path_history.bits;                         // Extract the path_history    
    return global_predictor[path_hist].isTaken();                            // return the MSBit
}

bool local_branch_prediction(const branch_record_c* br)
{
    uint pc = br->instruction_addr;                             // Current PC    
    uint pattern = local_history[pc].bits;                      // The local history pattern at the indx 
    return local_predictor[pattern].isTaken();    
}

void update_branch_prediction(const branch_record_c *br, uint outcome)
{
    if (br->is_return) {
        return;
    }
    update_local_branch_prediction(br, outcome);                // Update local predictor
    update_global_branch_prediction(br, outcome);               // Update global predictor
    update_prediction_chooser(br, outcome);
        
    path_history.push(outcome);                                 // Update path history
}

bool alpha_branch_prediction(const branch_record_c* br)
{
    if (br->is_return) {
        last_prediction.local_prediction = TAKEN;               // Store the local prediction
        last_prediction.global_prediction = TAKEN;              // Store the global prediction
        last_prediction.prediction = TAKEN;                     // Store the prediction
        return TAKEN;
    }

    bool prediction = NOT_TAKEN;
	bool local_prediction 	= local_branch_prediction(br); 		// Get the local branch prediction
	bool global_prediction	= global_branch_prediction(br);    	// Get the global branch prediction 

    bool take_global_predictor = prediction_chooser[path_history.bits].isTaken();             // If the MSB is 1 then take global predictor.
    
    if (take_global_predictor)
        prediction = global_prediction;
    else 
        prediction = local_prediction;     

    last_prediction.local_prediction = local_prediction;        // Store the local prediction
    last_prediction.global_prediction = global_prediction;      // Store the global prediction
    last_prediction.prediction = prediction;                    // Store the prediction

	return prediction;
}	

/* 
 ---------------------------------------------------------------------------------------------------------------------
 TARGET PREDICTOR 
 ---------------------------------------------------------------------------------------------------------------------
 */
#pragma mark - Target Predictor
uint get_branch_target_prediction(const branch_record_c* br)
{
    uint branch_target;
    if (br->is_indirect == false)
        branch_target = target_predictor.get_prediction(br->instruction_addr);
        
    if (br->is_return) {
        branch_target = r_stack.pop();
    }
    else if (br->is_call) {
            r_stack.push(br->instruction_next_addr);
        }
    return branch_target;
}

void update_branch_target_prediction(const branch_record_c* br, bool outcome, uint actual_target_address)
{
    if (br->is_return)                                          // Branch is return 
        return;                                                 // ignore
    target_predictor.update_prediction(br->instruction_addr, actual_target_address);
}

/* 
---------------------------------------------------------------------------------------------------------------------
SIMULATOR INTERFACE 
---------------------------------------------------------------------------------------------------------------------
*/

bool PREDICTOR::get_prediction(const branch_record_c* br, const op_state_c* os, uint *predicted_target_address)
{
    print_counter++;
    if(print_counter == 1)
        print_system_size();
        
    bool prediction = alpha_branch_prediction(br);                  // Perform alpha branch prediction
    *predicted_target_address = get_branch_target_prediction(br);   // Perform Target Prediction
    return prediction;
}

// Update the predictor after a prediction has been made.  This should accept
// the branch record (br) and architectural state (os), as well as a third
// argument (taken) indicating whether or not the branch was taken.
void PREDICTOR::update_predictor(const branch_record_c* br, const op_state_c* os, bool taken, uint actual_target_address)
{
    update_branch_prediction(br, taken);   
    update_branch_target_prediction(br, taken, actual_target_address);
}  